package br.edu.unifei.greedyiip;

import java.util.HashMap;
import java.util.Map;

import br.edu.unifei.mestrado.commons.graph.GraphWrapper;
import br.edu.unifei.mestrado.commons.graph.NodeWrapper;
import br.edu.unifei.mestrado.commons.graph.RelationshipWrapper;
import br.edu.unifei.mestrado.commons.partition.AbstractPartition;
import br.edu.unifei.mestrado.commons.partition.AbstractPartitionIndex;
import br.edu.unifei.mestrado.commons.partition.SimplePartition;

public abstract class GreedyIIP {

	private int k;

	private int runs;
	/**
	 * Lower bound on partition size
	 */
	private int L = 1;

	/**
	 * Upper bound on partition size
	 */
	private int R = 1;

	/**
	 * Indica a quantidade de nodes que cada partição tem.
	 */
	private Map<Integer, Integer> mapPartitionSize = new HashMap<Integer, Integer>();

	public GreedyIIP(int k, int runs) {
		this.k = k;
		this.runs = runs;
	}
	
	public abstract AbstractPartitionIndex getPartitionIndex();

	/**
	 * 
	 * @param coarsedGraph
	 * @param acceptNegative Usado para fazer o refinamento final, pois não deve aceitar ganhos negativos.
	 * @return
	 */
	public AbstractPartition executeIIP(GraphWrapper coarsedGraph, boolean acceptNegative) {

		// GraphWrapper graphLine = preprocess(originalGraph);//o grafo ja chega contraido

		GraphWrapper graphLine = coarsedGraph;

		AbstractPartition partitionLine = createStartingPartition(graphLine);
		AbstractPartition partition = partitionLine;

		GraphWrapper graph;

		int minGain = -(coarsedGraph.getSizeNodes() / 10);// TODO: melhorar esse calculo
		if(!acceptNegative) {
			minGain = 0;
		}
		
		int r;
		while (minGain <= 0) {
			r = runs;
			do {
				partition = partitionLine;
				graph = graphLine;
				partition = refine(graph, partitionLine, minGain);
				if (partition.getCutWeight() <= partitionLine.getCutWeight()) {
					r--;
				}
			} while (r >= 0);
			minGain++;// TODO: verificar quanto aumentar.
		}
		return partition;
	}

	private AbstractPartition createStartingPartition(GraphWrapper graph) {
		Map<Long, Boolean> edgesUsed = new HashMap<Long, Boolean>();
		Map<Long, Boolean> nodesUsed = new HashMap<Long, Boolean>();
		
		int setId = 0;

		AbstractPartition partition = new SimplePartition(AbstractPartition.NO_LEVEL, k, getPartitionIndex());
		for (NodeWrapper node : graph.getAllNodes()) {
			if (!nodesUsed.containsKey(node.getId())) {
				setId = getNextSetId(setId);
				node.setPartition(setId);
				nodesUsed.put(node.getId(), Boolean.TRUE);
				partition.addNodeToSet(setId, node);

				for (RelationshipWrapper edge : node.getRelationships()) {
					if (!edgesUsed.containsKey(edge.getId())) {
						edgesUsed.put(edge.getId(), Boolean.TRUE);
						NodeWrapper other = edge.getOtherNode(node);
						if (!nodesUsed.containsKey(other.getId())) {
							nodesUsed.put(other.getId(), Boolean.TRUE);

							setId = getNextSetId(setId);

							other.setPartition(setId);
							partition.addNodeToSet(setId, other);

							//se a aresta está no corte
							if(node.getPartition() != setId) {
								partition.addEdgeToCut(edge);
							}
						}
					}
				}
			}
		}
		return partition;
	}
	
	private int getNextSetId(int setId) {
		if(setId == k) {
			return 1;
		}
		return setId++;
	}

	void updateSizeBounds(GraphWrapper originalGraph, int k) {
		int sizeNodes = originalGraph.getSizeNodes();

		// UTIL: aplica variação de 10% para mais e para menos no tamanho das partições.
		L = (int) (sizeNodes / k * 0.9F);
		R = (int) (sizeNodes / k * 1.1F);
	}

	void initMapPartitionSize(int k) {
		for (int i = 0; i < k; i++) {
			mapPartitionSize.put(i, 0);
		}
	}

	private AbstractPartition refine(GraphWrapper graph, AbstractPartition partition, int minGain) {

		int costP = partition.getCutWeight();
		// AbstractPartition partitionLine = partition.clone();

		int bestGain = Integer.MIN_VALUE;
		int bestCi = AbstractPartition.NO_PARTITION;
		int bestPartition = AbstractPartition.NO_PARTITION;

		for (NodeWrapper node : graph.getAllNodes()) {
			int ci = node.getPartition();
			int sizeCi = mapPartitionSize.get(ci);
			if (sizeCi - 1 >= L) {
				for (int cj : mapPartitionSize.keySet()) {
					if (cj != ci) {
						int sizeCj = mapPartitionSize.get(cj);
						if (sizeCj + 1 <= R) {

							// muda o node de partição
							partition.removeNodeFromSet(ci, node);
							partition.addNodeToSet(cj, node);

							int costPL = partition.getCutWeight();
							int gain = costP - costPL;
							if (gain > bestGain && gain > minGain) {
								bestGain = gain;
								bestCi = ci;
								bestPartition = cj;
							}
							// volta o node na partição
							partition.addNodeToSet(ci, node);
							partition.removeNodeFromSet(cj, node);
						}
					}
				}
				if (bestPartition != AbstractPartition.NO_PARTITION) {
					// muda o node de partição
					partition.removeNodeFromSet(bestCi, node);
					partition.addNodeToSet(bestPartition, node);

					node.setPartition(bestPartition);
				}
			}
		}
		return partition;
	}

}
